from BaseTree import *


class BinaryTree(Tree):
    """二叉树基类，仍然是抽象基类"""

    # ----------------------------增加的方法----------------------------
    def left(self, p):
        """返回左子节点"""
        raise NotImplementedError('must be implemented by subclass')

    def right(self, p):
        """返回右子节点"""
        raise NotImplementedError('must be implemented by subclass')

    # ----------------------具体方法----------------------------------
    def sibling(self, p):
        """兄弟节点"""
        parent = self.parent(p)
        if parent is None:
            return None
        else:
            if p == self.left(parent):
                return self.right(parent)
            else:
                return self.left(parent)

    def children(self, p):
        """重写孩子方法"""
        if self.left(p) is not None:
            yield self.left(p)
        if self.right(p) is not None:
            yield self.right(p)

    def num_leaf(self,p):
        """统计叶子节点数量"""
        if self.num_children(p):
            return 1
        elif self.num_children(p) == 2:
            return self.num_leaf(self.left(p)) + self.num_leaf(self.right(p))
        elif self.left(p) is None:
            return self.num_leaf(self.right(p))
        else:
            return self.num_leaf(self.left(p))

    # -------------------------中序遍历------------------------------
    def inorder(self):
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

    def _subtree_inorder(self, p):
        if self.left(p) is not None:
            for other in self._subtree_inorder(self.left(p)):
                yield other

        yield p

        if self.right(p) is not None:
            for other in self._subtree_inorder(self.right(p)):
                yield other
